package selected;

import java.util.HashMap;
import java.util.Map;

public class J0826 {
    // 1 回文链表
    public ListNode reverse(ListNode head){
        ListNode prev = null, cur = head;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;
    }
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head, fast = head, cur = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = reverse(slow);
        while(mid != null){
            if(mid.val == cur.val){
                mid = mid.next;
                cur = cur.next;
            } else {
                return false;
            }
        }
        return true;
    }

    // 2 环形链表
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) return true;
        }
        return false;
    }

    // 3 合并链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode nHead = new ListNode(-1);
        ListNode cur  = nHead;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        if(list1 != null){
            cur.next = list1;
        }
        if(list2 != null){
            cur.next = list2;
        }
        return nHead.next;
    }

    // 4 两数相加
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int sum = 0, num = 0, carry = 0;
        ListNode nHead = new ListNode(-1);
        ListNode cur = nHead;
        while (l1 != null || l2 != null) {
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            sum = x + y + carry;
            num = sum % 10;
            carry = sum / 10;
            ListNode node = new ListNode(num);
            cur.next = node;
            cur = cur.next;

            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }

        if(carry == 1){
            ListNode node = new ListNode(1);
            cur.next = node;
        }

        return nHead.next;
    }

    // 5 删除倒数第n个节点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode slow = head;
        ListNode fast = head;
        while(n-- > 0){
            fast = fast.next;
            if(fast == null){
                return head.next;
            }
        }

        while(fast.next != null){
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return head;
    }

    // 6 两两交换链表中的节点
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        // 即就是使用当前段 head 去接下一段的头节点，再使用当前段的 next 去接当前段的 head 进行翻转
        ListNode next = head.next;
        head.next = swapPairs(next.next);
        next.next = head;
        return next;
    }

    // 7 k个一组翻转链表
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode groupPre = dummy;
        while(true){
            int kk = k;
            ListNode cur = groupPre;
            while(kk-- > 0 && cur != null){
                cur = cur.next;
            }
            if(cur == null){
                break;
            }
            ListNode groupNext = cur.next;
            ListNode prev = groupNext;
            ListNode tmp = null;
            cur = groupPre.next;
            // 翻转组内节点
            while(cur != groupNext){
                tmp = cur.next;
                cur.next = prev;
                prev = cur;
                cur = tmp;
            }
            // 处理该组前后节点与组内节点之间的来连接
            tmp = groupPre.next;
            groupPre.next = prev;
            groupPre = tmp;
        }
        return dummy.next;
    }

    // 8 输出链表环的入口节点
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        // 相遇点不一定是环的入口节点
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                break;
            }
        }
        // 先判断链表是否有环
        if(fast == null || fast.next == null){
            return null;
        }

        // 从头和slow一起走，相遇点就是环的入口节点
        fast = head;
        while(slow != fast){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }

    // 9 实现链表的深拷贝
    public ListNode copyRandomList(ListNode head) {
        // 通过哈希表建立映射关系
        Map<ListNode, ListNode> map = new HashMap<>();
        ListNode cur = head;
        // 建立新老节点之间的映射关系
        while(cur != null){
            ListNode node = new ListNode(cur.val);
            map.put(cur, node);
            cur = cur.next;
        }
        cur = head;
        // 建立新节点之间的 next、random关系
        while(cur != null){
            map.get(cur).next = map.get(cur.next);
//            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }


    public static void main(String[] args) {
        J0826 j0826 = new J0826();
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(1);
        System.out.println(j0826.isPalindrome(head));
    }
}
